package com.mlh.violent;

public class KnapsackProblem {
    public static void main(String[] args) {
        int[] weigh = { 1, 4, 3 };
        int[] value = { 1500, 3000, 2000 };
        int capacity = 4;
        solve(weigh,value,capacity);

    }

    public static void solve(int[]weigh,int[]value,int capacity){
        int num=weigh.length;//物品个数
        int[][] res=new int[num+1][capacity+1];
        // 初始化第一行和第一列 0物品 0容量  故值都为0
        for (int i = 0; i < res.length; i++) {
            res[i][0] = 0;
        }
        for (int j = 0; j < res[0].length; j++) {
            res[0][j] = 0;
        }
        for(int i=1;i<res.length;i++){//物品逐渐被解锁
            for(int j=1;j<res[0].length;j++){
                if(weigh[i-1]<=j){//背包能够装下这件物品
                    res[i][j]=Math.max(res[i-1][j],res[i-1][j-weigh[i-1]]+value[i-1]);
                    //path[i][j] = 1;  这个可以来记录当背包容量为j时，放什么物品价值最高
                }else{
                    //装不下这件物品
                    res[i][j]=res[i-1][j];
                }
            }
        }
        // 遍历二维数组并输出
        for (int i = 0; i < res.length; i++) {
            for (int j = 0; j < res[0].length; j++) {
                System.out.print(res[i][j] + " ");
            }
            System.out.println();
        }
    }
}
